package com.cty.kruskal;

import java.util.Arrays;

/*
 * 克鲁斯卡尔解决公交车站问题
 * */
public class Kruskal {
    char[] vertexs;
    int[][] weight;
    int numOfEdges = 0;
    public static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] weight = {
                {0, 12, INF, INF, INF, 16, 14},
                {12, 0, 10, INF, INF, 7, INF},
                {INF, 10, 0, 3, 5, 6, INF},
                {INF, INF, 3, 0, 4, INF, INF},
                {INF, INF, 5, 4, 0, 2, 8},
                {16, 7, 6, INF, 2, 0, 9},
                {14, INF, INF, INF, 8, 9, 0}};
        Kruskal kruskal = new Kruskal(vertexs, weight);
        kruskal.print();
        EData[] edges = kruskal.getEdges();
        System.out.println("排序前" + Arrays.toString(edges));
        kruskal.sortEdges(edges);
        System.out.println("排序" + Arrays.toString(edges));
        kruskal.getMinTree();
    }

    //最小生成树
    public void getMinTree() {
        int[] ends = new int[vertexs.length];
        EData[] rets = new EData[numOfEdges];
        int index = 0;
        EData[] edges = getEdges();
        sortEdges(edges);
        int p1;
        int p2;
        int m ;
        int n ;
        for (int i = 0; i < edges.length; i++) {
            p1 = getPosition(edges[i].start);
            p2 = getPosition(edges[i].end);
            m = getEnd(ends,p1);
            n = getEnd(ends,p2);
            if (m != n) {
                ends[m] = n;
                rets[index] = edges[i];
                index++;
            }
        }
        System.out.println("最小生成树是" + Arrays.toString(rets));
    }


    public Kruskal(char[] vertexs, int[][] weight) {
        this.weight = weight;
        this.vertexs = vertexs;
        for (int i = 0; i < weight.length; i++) {
            for (int j = i + 1; j < weight[i].length; j++) {
                if (weight[i][j] != INF) {
                    numOfEdges++;
                }
            }
        }
    }


    public void print() {
        for (int i = 0; i < weight.length; i++) {
            for (int j = 0; j < weight[i].length; j++) {
                System.out.printf("%12d", weight[i][j]);
            }
            System.out.println();
        }
    }

    //从小到大（冒泡排序）
    public void sortEdges(EData[] edges) {
        for (int i = 0; i < edges.length - 1; i++) {
            for (int j = 0; j < edges.length - 1 - i; j++) {
                if (edges[j].weight > edges[j + 1].weight) {
                    EData temp = edges[j + 1];
                    edges[j + 1] = edges[j];
                    edges[j] = temp;
                }
            }
        }
    }

    //返回该点所在的位置
    public int getPosition(char ch) {
        for (int i = 0; i < vertexs.length; i++) {
            if (ch == vertexs[i]) {
                return i;
            }
        }
        return -1;
    }

    //获取终点的方法
    public int getEnd(int[] ends, int i) {
        while (ends[i] != 0) {
            i = ends[i];
        }
        return i;
    }

    //获得边的数组
    public EData[] getEdges() {
        EData[] eData = new EData[numOfEdges];
        int index = 0;
        for (int i = 0; i < weight.length; i++) {
            for (int j = i + 1; j < weight[0].length; j++) {
                if (weight[i][j] != INF) {
                    eData[index] = new EData(vertexs[i], vertexs[j], weight[i][j]);
                    index++;
                }
            }
        }
        return eData;
    }
}
